package array

import (
	"log"
	"sort"
)

// https://leetcode-cn.com/problems/permutations/submissions/
// 按字典序全排列
// 算法: 递归
// 时间复杂度: O(n!)
func Permute(numArr []int) [][]int {
	if len(numArr) == 0 {
		return [][]int{}
	}
	sort.Ints(numArr)
	return recur([]int{}, numArr)
}

func recur(currentArr []int, remainArr []int) [][]int {
	log.Printf("[test] current arr: %v, remain arr: %v", currentArr, remainArr)
	if len(remainArr) == 0 {
		return [][]int{currentArr}
	}
	retArr := make([][]int, 0)
	for index, currentNum := range remainArr {
		copyArr := make([]int, len(currentArr)+1)
		copy(copyArr, currentArr)
		copyArr[len(currentArr)] = currentNum

		startCopyArr := make([]int, index)
		copy(startCopyArr, remainArr[0:index])
		if index != len(remainArr)-1 {
			retArr = append(retArr, recur(copyArr, append(startCopyArr, remainArr[index+1:]...))...)
		} else {
			retArr = append(retArr, recur(copyArr, startCopyArr)...)
		}
	}
	return retArr
}
